//实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。 
//
// 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 
//
// 必须 原地 修改，只允许使用额外常数空间。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [1,2,3]
//输出：[1,3,2]
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,1]
//输出：[1,2,3]
// 
//
// 示例 3： 
//
// 
//输入：nums = [1,1,5]
//输出：[1,5,1]
// 
//
// 示例 4： 
//
// 
//输入：nums = [1]
//输出：[1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 100 
// 0 <= nums[i] <= 100 
// 
// Related Topics 数组 
// 👍 987 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
/*思路：1、先判断有没有顺序上升 假设这个数在地k为位 那么从k往后这个数一定是减小的
*      2、从k往后找到刚好比k大一点的数 交换位置 此时可以发现剩余的数也还是顺序减小的
*      3、在把剩余减小的数倒置
*
*
* */
class Solution {
    public void nextPermutation(int[] nums) {
        int k=nums.length-1;
        while (k > 0&&nums[k]<=nums[k-1])
            k--;
        if(k<=0)
        {
            reverse(nums,0,nums.length - 1);
        }
        else {
            //注意理解为什么是k-1 因为在最开始判断时 不满足nums[k]<nums[k-1] 没有执行k--
            //此时 k 指向的是我们找到的那个数的上一个
            int t=k;
            while(t<nums.length&&nums[t]>nums[k-1])
                t++;
            //t多加了1
            swap(nums, k-1, t-1);
            reverse(nums, k, nums.length-1);
        }


    }

    void swap(int[] nums,int a,int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
    void reverse(int [] nums,int a,int b)
    {
        while(a<b)
        {
           swap(nums,a,b);
           a++;b--;
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)
